﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LabArray
{
    class Program
    {
        static void Main(string[] args)
        {

            while(true)
            {
                PrintArray(DetermineSort());
                Console.ReadKey();
            }
        }

        public static int PrintMenu() //1. Предлагается выбор метода сортировки
        {
            //Console.ForegroundColor = ConsoleColor.Blue; //Выбор цвета текста в консоли
            Console.WriteLine("Привет! Выбери метод сортировки, с помощью которого будет остортирован массив.");
            Console.WriteLine("Чтобы выбрать сортировку 'Пузырьком',       нажми 1.");
            Console.WriteLine("Чтобы выбрать сортировку 'Шелла',           нажми 2.");
            Console.WriteLine("Чтобы выбрать метод 'Быстрой сортировки',   нажми 3.");                
            
            int sortNumber = ReadIntFromConsole();
            Console.ReadKey();
            return sortNumber;
        }
               
        public static int GetArrayLength() //2. Предлагается ввести длину массива
        {
            //Console.ForegroundColor = ConsoleColor.Blue; //Выбор цвета текста в консоли
            Console.WriteLine("Введите количество элементов в массиве.");
            int arrayLength = ReadIntFromConsole();
            Console.ReadKey();
            return arrayLength;
        }

        public static int GetArrayType()  //3. Предлагается выбор вида массива (Отсортированный, Рандомный, Реверсеный)
        {
            //Console.ForegroundColor = ConsoleColor.Blue; //Выбор цвета текста в консоли
            Console.WriteLine("Определите какой массив следует отсортировать.");
            Console.WriteLine("Если хотите Отсортированный, нажмите 1.");
            Console.WriteLine("Если хотите Рандомный,       нажмите 2.");
            Console.WriteLine("Если хотите Реверсный,       нажмите 3.");

            int arrayType = ReadIntFromConsole();
            Console.ReadKey();
            return arrayType;
        }

        public static int ReadIntFromConsole()   //Получаем инт из консоли
                {
                    int retVal = 0;
                    bool inputIsCorrect = false;
                    while (!inputIsCorrect)
                    {
                        try
                        {                   
                            retVal = Int32.Parse(Console.ReadLine());                            
                            inputIsCorrect = true;
                            if (retVal <= 0)
                            {
                                throw new ArgumentException();
                            }
                        }
                        catch
                        {
                            Console.WriteLine("Введите натуральное число! Повторите ввод!");
                        }
                    }
                    return retVal;
                }  

        public static int[] CreateSortedArray(int arrayLength)  //Создание отсортированного массива
        {
            int[] result = new int[arrayLength];
            for (int i = 0; i < arrayLength; i++)
            {
                result[i] = i;
            }
            return result;
        }

        public static int[] CreateRandomArray(int arrayLength)  //Создание рандомного массива - Мин и Макс значения захардкоджены!!!
        {
            int[] array = new int[arrayLength];
            int min = 0;
            int max = 100;
            Random rnd = new Random();
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = rnd.Next(min, max);
            }
            return array;
        }

        public static int[] CreateUnSortedArray(int arrayLength)  //Создание реверсного (descending) массива
        {
            int[] array = new int[arrayLength];
            for (int i = 0; i < arrayLength; i++)
            {
                array[i] = (arrayLength - i - 1);
            }
            return array;
        }

        public static void PrintArray(int[] array)   //Вывод массива на экран
        {
            for (int i = 0; i < array.Length; i++)
            {
                Console.Write(" {0}", array[i]);
            }
            Console.WriteLine("");
        }

        //public static int[] DetermineSort()   //Определяем какую сортировку будем использовать
        //{
        //    int selectedSort = PrintMenu();
        //    int[] array = new int[0];
        //    switch (selectedSort)
        //    {
        //        case 1: ApplyBubbleSort();
        //            break;
        //        case 2: ApplyShellSort();
        //            break;
        //        case 3: ApplyQuickSort();
        //            break;
        //        default: Console.WriteLine("Сделайте выбор от 1 до 3.");
        //            Console.ReadKey();
        //            PrintMenu();
        //            break;
        //    }
        //    PrintArray(array);
        //    return array;
        //}

        public static int[] DetermineSort()   //Определяем какую сортировку будем использовать
        {
            int selectedSort = PrintMenu();
            int[] array = new int[0];
            if (selectedSort == 1 )
            {
                array = ApplyBubbleSort();
            }
            else if (selectedSort == 2)
            {
                array = ApplyShellSort();
            }
            else if (selectedSort == 3)
            {
                array = ApplyQuickSort();
            }
            return array;
        }

        public static int[] ApplyBubbleSort()   //Применение метода сортировки Пузырьком
        {
            int[] sortedArray = DetermineUseArrayType();
            DateTime startSort = DateTime.Now;
            int[] resultSort = BubbleSortArray(sortedArray);
            TimeSpan sortDuration = DateTime.Now - startSort;
            Console.WriteLine("Сортировка выполнена за {0} милисекунд", sortDuration.TotalMilliseconds);
            return resultSort;
        }

        public static int[] ApplyShellSort()   //Empty method
        {
            int[] sortedArray = DetermineUseArrayType();
            DateTime startSort = DateTime.Now;
            int[] resultSort = ShellSortArray(sortedArray);
            TimeSpan sortDuration = DateTime.Now - startSort;
            Console.WriteLine("Сортировка выполнена за {0} милисекунд", sortDuration.TotalMilliseconds);
            return resultSort;
        }

        public static int[] ApplyQuickSort()   //Empty method
        {
            int[] sortedArray = DetermineUseArrayType();
            DateTime startSort = DateTime.Now;
            int[] resultSort = QuickSortArray(sortedArray, 0, sortedArray.Length - 1);
            TimeSpan sortDuration = DateTime.Now - startSort;
            Console.WriteLine("Сортировка выполнена за {0} милисекунд", sortDuration.TotalMilliseconds);
            return resultSort;
        }

        

        //public static int[] DetermineUseArrayType()   //Определяем какой массив будем использовать
        //{
        //    int selectedArray = GetArrayType();
        //    int[] array = new int[0];
        //    switch (selectedArray)
        //    {
        //        case 1: ApplySortedArray();
        //            break;
        //        case 2: ApplyRandomArray();
        //            break;
        //        case 3: ApplyUnSortedArray();
        //            break;
        //        default: Console.WriteLine("Сделайте выбор от 1 до 3.");
        //            Console.ReadKey();
        //            GetArrayType();
        //            break;
        //    }
        //    return array;
        //}

        public static int[] DetermineUseArrayType()   //Определяем какой массив будем использовать
        {
            int selectedArray = GetArrayType();
            int[] array = new int[0];
            if (selectedArray == 1)
                array = ApplySortedArray();
            else if (selectedArray == 2)
                array = ApplyRandomArray();
            else if (selectedArray == 3)
                array = ApplyUnSortedArray();
            else GetArrayType();
            return array;
        }

        public static int[] ApplySortedArray()  //Создаем сортированный массив заданной длины для его дальнейшей сортировки
        {
            int arrayLength = GetArrayLength();
            int[] array = CreateSortedArray(arrayLength);
            PrintArray(array);
            Console.WriteLine();
            return array;
        }

        public static int[] ApplyRandomArray()  //Создаем рандомный массив заданной длины для его дальнейшей сортировки
        {
            int arrayLength = GetArrayLength();
            int[] array = CreateRandomArray(arrayLength);
            PrintArray(array);
            Console.WriteLine();
            return array;
        }

        public static int[] ApplyUnSortedArray()  //Создаем обратно сортированный массив заданной длины для его дальнейшей сортировки
        {
            int arrayLength = GetArrayLength();
            int[] array = CreateUnSortedArray(arrayLength);
            PrintArray(array);
            Console.WriteLine();
            return array;
        }
        
        public static int[] BubbleSortArray(int[] array)  //Bubble Sort
        {
            int length = array.Length;
            int temp = 0;
            for (int i = 0; i < length; i++)
            {
                for (int j = i + 1; j < length; j++)
                {
                    if (array[i] > array[j])
                    {
                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
            }
            return array;
        }

        public static int[] ShellSortArray(int[] array)   //Shell Sort
           {
              int j;
              int step = array.Length / 2;
              while (step > 0)
              {
                  for(int i = 0; i < (array.Length - step); i++)
                  {
                      j = i;
                      while ((j >= 0) && (array[j] > array[j + step]))
                      {
                          int tmp = array[j];
                          array[j] = array[j + step];
                          array[j + step] = tmp;
                          j--;
                      }
                  }
                  step = step / 2;
               }
               return array;
      	    }

        public static int[] QuickSortArray(int[] array, int l, int r)   //Quick Sort //- Диапазон сортировки захардкоджен на всю длину массива
        {
            int temp;
            int x = array[l + (r - l) / 2];
            //запись эквивалентна (l+r)/2, но не вызввает переполнения на больших данных
            int i = l;
            int j = r;
            //код в while обычно выносят в процедуру particle
            while (i <= j)
            {
                while (array[i] < x) i++;
                while (array[j] > x) j--;
                if (i <= j)
                {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    i++;
                    j--;
                }
            }
            if (i < r)
                QuickSortArray(array, i, r);

            if (l < j)
                QuickSortArray(array, l, j);

            return array;
        }

                
        //Сортировка - Быстрая сортировка
        //int partition(int[] m, int a, int b)
        //{
        //    int i = a;
        //    for (int j = 0; j < b; j++)
        //    {
        //        if (m[j].CompareTo(m[b]) <= 0)
        //        {
        //            int t = m[i];
        //            m[i] = m[j];
        //            m[j] = t;
        //            i++;
        //        }
        //    }
        //}
        //return i - 1;
    }
    
}

